// Copyright (c) 2006, Inc.
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
//
// Author: arvin.chen
//
//

#ifndef ALGORITHM_SORT_QUICK_RECURSION_H_
#define ALGORITHM_SORT_QUICK_RECURSION_H_

#ifndef ALGORITHM_SORT_BASE_H_
#include "algorithm/sort/base.h"
#endif

namespace algorithm {
	namespace sort {

		template<typename T>
		class QuickRecursion : public Base<T> {
		public:

			/**
			* Construction
			*
			* @param
			* @return
			*/
			QuickRecursion() :
				Base<T>::Base(kQuickRecursion)
			{

			}

			/**
			* Destruction
			*
			* @param VOID
			* @return
			*/
			~QuickRecursion()
			{

			}

			/**
			* sort
			*
			* @param T arr[]
			* @param int len
			* @return T
			*/
			virtual T* sort(T arr[], int len)
			{
				if (nullptr == arr || 1 >= len) return arr;
				SortRecursion(arr, 0, len - 1);
				return arr;
			}

		protected:
			/**
			* Assignment
			*
			* @param const QuickRecursion& cbase
			* @return QuickRecursion&
			*/
			QuickRecursion& operator=(const QuickRecursion& cbase);

			/**
			* Copy Construction
			*
			* @param const QuickRecursion& cbase
			* @return
			*/
			QuickRecursion(const QuickRecursion& cbase);

		private:

			/**
			* SortRecursion
			*
			* @param T arr[]
			* @param int left
			* @param int right
			* @return void
			*/
			T* SortRecursion(T arr[], int left, int right) {
				// Get the position of the axis element
				if (left < right) {
					// Separate the large array into two arrays
					int mid = QuickArr(arr, left, right);
					SortRecursion(arr, left, mid - 1);
					SortRecursion(arr, mid + 1, right);
				}
				return arr;
			}

			/**
			* QuickArr
			* Get the position of the axis element
			*
			* @param T arr[]
			* @param int h
			* @param int i
			* @return int
			*/
			int QuickArr(T arr[], int left, int right) {
				T pivot = arr[left];
				int i = left + 1;
				int j = right;
				while (true) {
					// Find the first element position less than or equal to pivot to the right
					while (i <= j && arr[i] <= pivot) i++;
					// Find the first element position greater than or equal to pivot to the left
					while (i <= j && arr[j] >= pivot) j--;
					if (i >= j)
						break;
					//Exchange the positions of the two elements so that the element on the left is not greater than pivot, and the one on the right is not less than pivot
					std::swap(arr[i], arr[j]);
					// 					T temp = arr[i];
					// 					arr[i] = arr[j];
					// 					arr[j] = temp;
				}
				// Make the central axis elements in an orderly position
				std::swap(arr[left], arr[j]);
				// 				arr[left] = arr[j];
				// 				arr[j] = pivot;
				return j;
			}

		public:
		protected:
		private:

		};
	} // namespace algorithm 
} // namespace sort


#endif  // ALGORITHM_SORT_QUICK_RECURSION_H_
